package everydayGrade.t5;

import CommonStructure.TreeNode;

/**
 * @Author: Siantar
 * @Date: 2023-11-25-8:52
 * @Description: 1.0
 */
public class T1457 {
    public int pseudoPalindromicPaths(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode node, int mark) {
        if (node == null) return 0;
        mark ^= 1 << node.val;
        if (node.left == null && node.right == null) return isPalindrome(mark) ? 1 : 0;
        int cnt = 0;
        cnt += dfs(node.left, mark);
        cnt += dfs(node.right, mark);
        return cnt;
    }

    public boolean isPalindrome(int mark) {
        if (mark == 0) return true;
        while ((mark & 1) != 1) {
            mark >>= 1;
        }
        return mark == 1;
    }
}
